package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 单词搜索
 * @date 2022/8/21 13:42
 */
public class Demo24 {
    boolean find;
    public boolean exist(char[][] board, String word) {
        if(board==null){
            return false;
        }
        int length=board.length;
        int with=board[0].length;
        boolean[][] visited = new boolean[length][with];
        find = false;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < with; j++) {
                    trackBack(i,j,board,visited,0,word);
                }
            }
        return find;
        }

    private void trackBack(int i, int j, char[][] board, boolean[][] visited, int index, String word) {
        if(i<0||i==board.length||j<0||j==board[0].length||visited[i][j]||board[i][j]!=word.charAt(index)||find){
            return;
        }
        if(index == word.length()-1){
            find = true;
            return;
        }
        visited[i][j] = true;  // 修改当前节点状态
        trackBack(i+1, j, board,  visited, index+1,word);  // 遍历子节点
        trackBack(i-1, j, board,  visited, index+1,word);
        trackBack(i, j+1, board,  visited, index+1,word);
        trackBack(i, j-1, board,  visited, index+1,word);
        visited[i][j] = false; // 撤销修改
    }
}

